package heightChecker;

import java.util.Arrays;

public class Solution {
    public int heightChecker(int[] heights) {
//        int []expect = Arrays.copyOf(heights,heights.length);
//        Arrays.sort(expect);
//        int count = 0;
//        for (int i = 0; i < heights.length; i++) {
//            if(expect[i]!=heights[i]){
//                count++;
//            }
//        }
//        return count;

        // 计数排序
        int[] arr = new int[101];
        for (int v: heights) {
            arr[v]++;
        }
        // 相当于桶排序
        int ans = 0;
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            while(arr[i]>0){
                arr[i]--;
                if(heights[index]!=arr[i]){
                    ans++;
                }
                index++;
            }
        }
        return ans;
    }
}
